package com.guaoran.algorithm.binary.search;

/**
 * @Auth gucheng
 * @Desc 通过二分法查找有序数组中的最小值
 *
 * @Date 2021/1/7 下午3:51
 */
public class FindMinimumInRotatedSortedArray {

    public static void main(String[] args){
        System.out.println(findMin(new int[]{3, 4, 5, 1, 2}));
        System.out.println(findMin2(new int[]{1,3,3}));
    }

    /**
     * 不包含重复 ==》 [4,5,6,7,0,1,2]
     * https://leetcode.com/problems/find-minimum-in-rotated-sorted-array
     * @param nums
     * @return
     */
    private static int findMin(int[] nums){
        if(nums == null || nums.length == 0){
            return 0;
        }

        int start = 0;
        int end = nums.length -1;
        int mid;
        while(start + 1 < end){
            mid = start + (end - start)/2;
            if(nums[mid] >= nums[start]){
                if(nums[mid] >= nums[end]){
                    start = mid;
                }else {
                    end = mid;
                }
            }else{
                end = mid;
            }
        }
        return Math.min(nums[start],nums[end]);
    }

    /**
     * 包含重复元素 ==》 [1,3,3] 、[2,2,2,0,1] 、[1,3,5]
     * @param nums
     * @return
     */
    private static int findMin2(int[] nums){
        if(nums == null || nums.length == 0){
            return 0;
        }
        int start = 0;
        int end = nums.length -1;
        int mid;
        while(start + 1 < end){
            mid = start + (end - start)/2;
            if(nums[mid] > nums[end]){
                start = mid;
            }else if(nums[mid] < nums[end]){
                end = mid;
            }else{
                end --;
            }
        }
        return Math.min(nums[start],nums[end]);
    }
}
